1. Field of Invention
The disclosure relates to ternary storage of data items, multiple of which may need to be associated with a single bit code, and more particularly to the ternary identification of frequent ranges associated with rules contained with Access Control Lists (ACLs).
2. Related Art
Communication devices, such as routers and servers are commonly used in both corporate and personal settings to handle data and network throughput. These communication devices provide users with cross-communication abilities between devices, as well as the ability to communicate over larger networks like the internet.
In order to properly process incoming data packets, a communication device must accurately identify the actions to be performed on each packet. The actions to be performed are stored as rules associated with an Access Control List (ACL). The communication device selects a rule to be performed on a received packet based on the packet's source port and/or destination port. However, each rule may be applicable to several ports, and consequently can require several data entries in a Ternary Content Addressable Memory (TCAM).
TCAMs are memory devices used for representing ternary data entries. A ternary entry consists not only of 0 s and 1 s, but also x (immaterial if a 0 or a 1).
One conventional method for storing such ranges is known as prefix expansion. In this method, if the range field is 16 bits wide and the communication device is representing a range (2, 4), then it represents the range using two entries: Entry 1—000000000000001x; and Entry 2—0000000000000100. Using this approach, if the range field is W bits wide, then the worst case number of entries required to represent the range is 2 W-2.
Because of the large number of entries required, this representation poses a significant storage problem for larger ranges. For example, if a particular ACL requires storing both a source port and a destination port, and the width of the ports are 16 bits each, then the number of entries required is (2*16−2)*(2*16−2)=30*30=900 entries. As such, the conventional approach requires a significant number of entries to represent only a single range. Other approaches suffer from similar problems.